#include <iostream>
#include <vector>
#include <climits>
#include <deque>
using namespace std;

struct BigNum{
	deque<int> data;
	BigNum(unsigned long long n){
		while(n > 9){
			data.push_front(n%10);
			n = n/10;
		}
		data.push_front(n);
	}
	explicit BigNum() {}
};



BigNum operator+(BigNum lhs, BigNum rhs){
	BigNum result;

	while(lhs.data.size() != rhs.data.size()){
		if(lhs.data.size() < rhs.data.size())
			lhs.data.push_front(0);
		else
			rhs.data.push_front(0);
	}

	int remainder = 0;
	for(int l = lhs.data.size()-1, r = rhs.data.size()-1; l >= 0 && r >= 0; l--, r--){
		//add last nums and copy into the new one
		int sum = lhs.data[l] + rhs.data[r] + remainder;
		if(sum > 9){
			result.data.push_front(sum % 10);
			remainder = 1;
		}
		else{
			result.data.push_front(sum);
			remainder = 0;
		}
	}

	if(remainder != 0){
		result.data.push_front(1);
	}

	return result;
}

ostream& operator<<(ostream& os, const BigNum& bn){
	for(size_t i =0; i < bn.data.size(); ++i)
		os << bn.data[i];
	return os;
}

static int CACHE_SIZE = 1000;
vector<BigNum> cache;
BigNum count(unsigned n){ //n should be 1 <= n <= 1000
	//cache check
	if(n < cache.size()){
		return cache[n];
	}
	else{
		BigNum val = count(n-1)+count(n-1)+count(n-2)+count(n-3);
		if(n == cache.size()){	//my cache MUST be in numerical order for this to work
			cache.push_back(val);
		}
		return val;
	}
}

int main(){
	cache.push_back(0);	// count(0) is invalid
	cache.push_back(2);	//count(1)
	cache.push_back(5);	//cache(2)
	cache.push_back(13);	//cache(3)
	for(int i = 4; i < CACHE_SIZE; ++i){
		count(i);
	}

	int input;
	while(cin >> input)
		cout << count(input) << endl;
}
